Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.
You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.
We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.
Example 1:
Input: root = [4,2,5,1,3]Output: [1,2,3,4,5] Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.
Example 2:
Input: root = [2,1,3] Output: [1,2,3]
Example 3:
Input: root = [] Output: [] Explanation: Input is an empty tree. Output is also an empty Linked List.
Example 4:
Input: root = [1] Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000- All the values of the tree are unique.
Average Rating: 4.59 (71 votes)
Solution
How to traverse the tree
There are two general strategies to traverse a tree:
-
Depth First Search (
DFS)In this strategy, we adopt the
depthas the priority, so that one would start from a root and reach all the way down to certain leaf, and then back to root to reach another branch.The DFS strategy can further be distinguished as
preorder,inorder, andpostorderdepending on the relative order among the root node, left node and right node. -
Breadth First Search (
BFS)We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.
On the following figure the nodes are numerated in the order you visit them,
please follow 1-2-3-4-5 to compare different strategies.
Here the problem is to implement DFS inorder traversal
in a textbook recursion way because of in-place
requirement.
Approach 1: Recursion
Algorithm
Standard inorder recursion follows left -> node -> right order,
where left and right parts are the recursion calls and
node part is where all processing is done.
Processing here is basically to link the previous node with the current one, and because of that one has to track the last node which is the largest node in a new doubly linked list so far.
One more detail : one has to keep the first, or the smallest, node as well to close the ring of doubly linked list.
Here is the algorithm :
-
Initiate the
firstand thelastnodes as nulls. -
Call the standard inorder recursion
helper(root):-
If node is not null :
-
Call the recursion for the left subtree
helper(node.left). -
If the
lastnode is not null, link thelastand the currentnodenodes. -
Else initiate the
firstnode. -
Mark the current node as the last one :
last = node. -
Call the recursion for the right subtree
helper(node.right).
-
-
-
Link the first and the last nodes to close DLL ring and then return the
firstnode.
Implementation
Complexity Analysis
-
Time complexity : O(N) since each node is processed exactly once.
-
Space complexity : O(N). We have to keep a recursion stack of the size of the tree height, which is O(logN) for the best case of completely balanced tree and O(N) for the worst case of completely unbalanced tree.
August 9, 2019 11:17 AM
Java iterative solution.
public Node treeToDoublyList(Node root) {
if( root == null) return root;
Node dummy = new Node(0);
Node prev = dummy;
Stack<Node> stack = new Stack();
Node curr = root;
while(!stack.isEmpty()|| curr != null){
while(curr!= null){
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
prev.right = curr;
curr.left = prev;
prev = curr;
curr = curr.right;
}
dummy.right.left = prev;
prev.right = dummy.right;
return dummy.right;
}
}
February 20, 2020 11:52 AM
For folks saying it is not in-place, if I am not wrong, academically in-place means mutating the input and not returning newly allocated data. That is you can use extra space but in the end the returned value should not be something newly created but instead all changes done in the given input only.
March 28, 2019 3:48 AM
This is not O(1) space. It is O(tree depth), so O(n) worst case and O(log(n)) average case.
Keep in mind that the recursive call stack takes space, and there will be (at maximum depth) one stack from for each level in the tree.
August 21, 2019 5:10 AM
Approach 1: Iteration
Python3
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root:
return None
stack = [root]
first, curr, last = None, root.left, None
while curr or stack:
if curr:
stack.append(curr)
curr = curr.left
continue
if stack:
curr = stack.pop()
if not first:
first = curr
if last:
last.right = curr
curr.left = last
last = curr
curr = curr.right
first.left = last
last.right = first
return first
Time complexity : O(N)
Space complexity : O(N)
January 20, 2020 6:15 AM
Another way is to do inOrder traversal and add all nodes to a arrayList. Then do linkage later.
Last Edit: March 10, 2020 9:31 AM
Here is my O(1) space solution using Morris In Order Traversal
https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/discuss/534869/JavaScript-Morris-In-Order-Traversal-O(n)-Time-O(1)-Space
var treeToDoublyList = function(root) {
if (!root) return root;
let head = new Node();
let last = head;
let node = root;
while (node) {
if (node.left) {
let predecessor = node.left;
while (predecessor.right && predecessor.right !== node) {
predecessor = predecessor.right;
}
if (predecessor.right === null) {
predecessor.right = node;
node = node.left;
} else {
last.right = node;
node.left = last;
last = node;
// predecessor.right = null; <= this is the line for normal
node = node.right;
}
} else {
last.right = node;
node.left = last;
last = node;
node = node.right;
}
}
last.right = head.right;
head.right.left = last;
return head.right;
};
December 27, 2019 10:26 AM
Wow, amazing clean code. Respect!
November 22, 2020 8:57 PM
Great solution. Basically we are using inorder traversal and just following the order of its traversal to update the last node.
May 3, 2020 3:39 PM
Why is this related with Divide and Conquer?
January 19, 2020 5:54 AM
Folks, I think "in-place" here ONLY means do not use inorder traversal first to go through all the nodes. It does not mean not use recursion or extra space. Apparently leetcode has different definitions of in-place with all the others.
You don't have any submissions yet.
xxxxxxxxxx/*// Definition for a Node.class Node {public: int val; Node* left; Node* right; Node() {} Node(int _val) { val = _val; left = NULL; right = NULL; } Node(int _val, Node* _left, Node* _right) { val = _val; left = _left; right = _right; }};*/class Solution {public: Node* treeToDoublyList(Node* root) { }};